package com.mgq.algorithm.dp;

/**
 * 给一个N*M参数,表示的是N*M的格子,给定(a,b)表示Bob的初始位置,给定K表示经过k步,Bob走的方式是上下左右
 * Bob从(a,b)经过k步,最后活下来的概率是多少?(活下来的条件是不越界)
 */
public class BobDie {
    public static void main(String[] args) {
        System.out.println(bobDie(4, 4, 1, 1, 4));
    }

    /**
     * bob生存的概率
     *
     * @param N
     * @param M
     * @param a
     * @param b
     * @param k
     * @return
     */
    public static String bobDie(int N, int M, int a, int b, int k) {
        long all = (long) Math.pow(4, k);
        // long live = process(N, M, a, b, k);
        long live = dp(N, M, a, b, k);
        double v = livePosibility2(a, b, k, N, M);
        return live / gcd(live, all) + "/" + all / gcd(live, all);
    }

    /**
     * 计算最大公约数
     *
     * @param a
     * @param b
     * @return
     */
    public static long gcd(long a, long b) {
        if (a % b == 0)
            return b;
        return gcd(b, a % b);
    }

    /**
     * @param N
     * @param M
     * @param row
     * @param col
     * @param rest
     * @return
     */
    public static long process(int N, int M, int row, int col, int rest) {
        //越界
        if (row < 0 || row == N || col < 0 || col == M) {
            return 0;
        }
        if (rest == 0) {
            return 1;
        }
        long live = process(N, M, row - 1, col, rest - 1); //左
        live += process(N, M, row + 1, col, rest - 1);//右
        live += process(N, M, row, col - 1, rest - 1);//下
        live += process(N, M, row, col + 1, rest - 1);//上
        return live;
    }

    /**
     * 变量 row,col,rest
     *
     * @param N
     * @param M
     * @param row
     * @param col
     * @param rest
     * @return
     */
    public static long dp(int N, int M, int row, int col, int rest) {
        int[][][] dp = new int[N][M][(rest + 1)];
        //rest==0,return 1
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                dp[j][i][0] = 1;
            }
        }
        //找出一个普遍位置,分析依赖
        System.out.println("dp.length:"+dp.length);
        System.out.println("rest:"+rest);
        //注意: 在多维数组中,调用dp.length length方法返回的是行数
        for (int i = 1; i <= rest; i++) {
            for (int j = 0; j < M; j++) {
                for (int k = 0; k < N; k++) {
                    dp[k][j][i] = getValue(dp, k - 1, j, i - 1, N, M);
                    dp[k][j][i] += getValue(dp, k + 1, j, i - 1, N, M);
                    dp[k][j][i] += getValue(dp, k, j - 1, i - 1, N, M);
                    dp[k][j][i] += getValue(dp, k, j + 1, i - 1, N, M);
                }
            }
        }
        return dp[row][col][rest];
    }

    public static int getValue(int[][][] dp, int row, int col, int step, int N, int M) {
        if (row < 0 || row == N || col < 0 || col == M) {
            return 0;
        }
        return dp[row][col][step];

    }

    public static double livePosibility2(int row, int col, int k, int N, int M) {
        long[][][] dp = new long[N][M][k + 1];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                dp[i][j][0] = 1;
            }
        }
        for (int rest = 1; rest <= k; rest++) {
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < M; c++) {
                    dp[r][c][rest] = pick(dp, N, M, r - 1, c, rest - 1);
                    dp[r][c][rest] += pick(dp, N, M, r + 1, c, rest - 1);
                    dp[r][c][rest] += pick(dp, N, M, r, c - 1, rest - 1);
                    dp[r][c][rest] += pick(dp, N, M, r, c + 1, rest - 1);
                }
            }
        }
        return (double) dp[row][col][k] / Math.pow(4, k);
    }

    public static long pick(long[][][] dp, int N, int M, int r, int c, int rest) {
        if (r < 0 || r == N || c < 0 || c == M) {
            return 0;
        }
        return dp[r][c][rest];
    }
}
